package com.xcc.dataStructures.demo14_algapplication;

import java.util.Arrays;

/**
 * 迪杰斯特拉算法
 *   以图中一个顶点作为初始点，求这个顶点到所有点的最小距离
 *   思路:1，构建一个vistedvetex对象（a，pre数组记录到达当前顶点的上一个顶点索引;b，already数组记录当前顶点是否被访问;c，dis记录从初始顶点出发到达当前顶点的距离）
 *       2，初始化根据初始顶点，构建：除初始顶点以外所有dis均为最大值(65535)，除初始顶点以外的所有顶点均为被访问
 *       3，以index(第一次index为初始顶点，之后均为获取当前dis数组中未被访问的最短距离为index，并标记当前index为已访问)
 *          作为基准点，获取当前dis中index的值(该值则为从初始结点到index的距离) + index到i(遍历图变化) 距离之和 记为len,
 *          用len与dis中i的值进行比较：如果len < dis[i],则说明以index作为基准点 更为合适，此时更新dis[i] = len ; pre[i] = index
 */
public class Demo08_Dijkstra {

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;// 表示不可以连接
        matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, N, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, N, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, N, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, N};

        Graph graph = new Graph(vertex, matrix);
        graph.dsj(6);

    }

}

/**
 * 构建图对象
 */
class Graph {

    private char[] vertex;
    private int[][] matrix;
    private VisitedVetex vv;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    /**
     * 迪杰斯特拉算法
     *
     * @param index 初始顶点的坐标
     */
    public void dsj(int index) {
        //初始化visitedVetex
        vv = new VisitedVetex(index, vertex.length);
        //以index作为介质，更新visitedvetex中的dis和pre
        update(index);
        //记录当前存储在dis数组中 并 未被访问的最小节点的距离
        int i;
        //如果当前i==-1 ，则表示dis数组中所有的数据均被访问过
        while ((i = vv.updateArr()) != -1) {
            //以i作为介质  更新vv
            update(i);
        }

        //打印
        vv.show();
    }

    /**
     * 更新以当前结点为 介质 的visitedvetex的 dis和pre数组
     *
     * @param index 当前结点的索引
     */
    private void update(int index) {
        //遍历以index作为结点  获取 与其连接的所有结点
        for (int i = 0; i < matrix[index].length; i++) {
            //len为  从index到i结点的邻接距离 + 存储在dis数组中的起始点到index的距离
            int len = matrix[index][i] + vv.dis[index];
            //如果len < 存储在dis数组中的起始点到i 结点的距离  并且当前i结点未被访问过(只有i在dis数组中为最小的数时才会被访问)
            if (len < vv.dis[i] && !vv.isVisited(i)) {
                //更新dis数组中 起始点到i的距离为len
                vv.updateDis(i, len);
                //修改当前i结点的前驱结点为index
                vv.updatePre(i, index);
            }
        }
    }


}

/**
 * 访问对象
 */
class VisitedVetex {
    private static int Max = 65535;

    //记录各个顶点是否已经被访问。1表示访问过，0表示为访问过
    int[] already_arr;
    //每个下标对应的值为前一个顶点下标，会动态更新
    int[] pre_visited;
    //记录出发顶点到其他所有顶点的距离，比如G作为出发顶点，机会记录G到其它顶点的距离，会动态更新，将最短距离存放到dis中
    int[] dis;

    public VisitedVetex(int index, int len) {
        already_arr = new int[len];
        pre_visited = new int[len];
        dis = new int[len];

        Arrays.fill(dis, Max);
        dis[index] = 0;
        already_arr[index] = 1;
    }

    /**
     * 当前用户是否被访问
     * 访问过返回true
     * 未被访问返回false
     */
    public boolean isVisited(int index) {
        return already_arr[index] == 1;
    }

    /**
     * 更新当前的访问状态
     * 每次获取的时候得到的值都不一样，每次都获取当前最短的并且未被访问的dis的下标
     * 这样能保证每次以这个最短下标为介质，获取的len为尽可能的小
     *
     * @return 返回距离最短索引下标，如果当前dis数组均已经被访问过则返回-1(作为循环停止的条件)
     */
    public int updateArr() {
        int min = 65535, minIndex = -1;
        for (int i = 0; i < dis.length; i++) {
            if (min >= dis[i] && !isVisited(i)) {
                min = dis[i];
                minIndex = i;
            }
        }
        if (minIndex > -1) {
            already_arr[minIndex] = 1;
        }
        return minIndex;
    }

    /**
     * 修改当前顶点的距离
     *
     * @param index 需要修改节点的索引
     * @param val   被修改的值
     */
    public void updateDis(int index, int val) {
        dis[index] = val;
    }

    /**
     * 获取距离
     *
     * @param index 获取的索引
     * @return 返回距离
     */
    public int getDis(int index) {
        return dis[index];
    }

    /**
     * 修改前驱节点值
     *
     * @param index 需要修改节点的索引
     * @param val   被修改的前驱节点下标
     */
    public void updatePre(int index, int val) {
        pre_visited[index] = val;
    }

    @Override
    public String toString() {
        return "already_arr=" + Arrays.toString(already_arr) +
                "\npre_visited=" + Arrays.toString(pre_visited) +
                "\ndis=\t\t" + Arrays.toString(dis);
    }

    public void show() {
        System.out.println("==========================");
        //输出 already_arr
        for (int i : already_arr) {
            System.out.print(i + " ");
        }
        System.out.println();

        //输出 pre_visited
        for (int i : pre_visited) {
            System.out.print(i + " ");
        }
        System.out.println();

        //输出 dis
        for (int i : dis) {
            System.out.print(i + " ");
        }
        System.out.println();

        //为了好看最后的最短距离，我们处理
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ") ");
            } else {
                System.out.println("N ");
            }
            count++;
        }
        System.out.println();
    }
}
